package com.xxwy.maxheap.practice.leetcode;

import java.util.*;

/**
 * @author xxwy
 */
public class TopKFrequent3 {
    public List<Integer> topKFrequent(int[] nums, int k) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                map.put(nums[i], map.get(nums[i]) + 1);
            } else {
                map.put(nums[i], 1);
            }
        }

        //java内置的PriorityQueue是最小堆
        PriorityQueue<Integer> pq = new PriorityQueue<>(k,
                Comparator.comparingInt(map::get)
        );
        for (Integer key : map.keySet()) {
            if (pq.size() < k) {
                pq.add(key);
            } else if (map.get(key) > map.get(pq.peek())) {
                pq.remove();
                pq.add(key);
            }
        }
        LinkedList<Integer> integers = new LinkedList<>();
        while (!pq.isEmpty()){
            integers.add(pq.remove());
        }
        return integers;
    }
}
